#  冒泡排序
import random
from utils.array_utils import check


def bubbles_01(nums):
    count = 0
    for j in range(len(nums)):
        for i in range(1, len(nums)):
            count += 1
            if nums[i - 1] > nums[i]:
                nums[i - 1], nums[i] = nums[i], nums[i - 1]
    return count


# 加入sorted标记
def bubbles_01_a(nums):
    count = 0
    for j in range(len(nums)):
        is_sorted = True
        for i in range(1, len(nums)):
            count += 1
            if nums[i - 1] > nums[i]:
                nums[i - 1], nums[i] = nums[i], nums[i - 1]
                is_sorted = False
        if is_sorted:
            break
    return count


# 加入sorted标记 和 已排序右边界flag
def bubbles_02(nums):
    count = 0
    for j in range(len(nums)):
        for i in range(1, len(nums) - j):
            count += 1
            if nums[i - 1] > nums[i]:
                nums[i - 1], nums[i] = nums[i], nums[i - 1]
    return count


def bubbles_02_a(nums):
    count = 0
    flag = len(nums)
    for j in range(len(nums)):
        is_sorted = True
        for i in range(1, flag):
            count += 1
            if nums[i - 1] > nums[i]:
                nums[i - 1], nums[i] = nums[i], nums[i - 1]
                is_sorted = False
                flag = i
        if is_sorted:
            break
    return count


def bubbles_03(nums):
    ''' 鸡尾酒排序 从首尾两头冒泡'''
    count = 0
    length = len(nums)
    for j in range(length):
        for i in range(1 + j, length - j):
            count += 1
            if nums[i - 1] > nums[i]:
                nums[i - 1], nums[i] = nums[i], nums[i - 1]
            if nums[length - i] < nums[length - i - 1]:
                nums[length - i], nums[length - i - 1] = nums[length - i - 1], nums[length - i]
            # print(nums[1 + j:length - j])
    return count


def bubbles_03_a(nums):
    ''' 鸡尾酒排序 加入两个sorted标记'''
    count = 0
    length = len(nums)
    for j in range(length):
        l_sorted = True
        r_sorted = True
        for i in range(1 + j, length - j):
            count += 1
            if nums[i - 1] > nums[i]:
                nums[i - 1], nums[i] = nums[i], nums[i - 1]
                r_sorted = False

            if nums[length - i] < nums[length - i - 1]:
                nums[length - i], nums[length - i - 1] = nums[length - i - 1], nums[length - i]
                l_sorted = False
            # print(nums[1 + j:length - j])
        if l_sorted or r_sorted:
            break
    return count


def bubbles_03_b(nums):
    ''' 鸡尾酒排序 加入两个sorted标记和左右两个已排序边界标记lflag,rflag'''
    count = 0
    length = len(nums)
    lflag = 0
    rflag = length
    for j in range(length):
        l_sorted = True
        r_sorted = True
        for i in range(1 + j, length - j):
            count += 1
            # 从左侧交换 有序标记在右侧
            if nums[i - 1] > nums[i]:
                nums[i - 1], nums[i] = nums[i], nums[i - 1]
                rflag = i
                r_sorted = False

            # 从右侧交换
            if nums[length - i] < nums[length - i - 1]:
                nums[length - i], nums[length - i - 1] = nums[length - i - 1], nums[length - i]
                # if nums[lflag - i] < nums[lflag - i - 1]:
                #     nums[lflag - i], nums[lflag - i - 1] = nums[lflag - i - 1], nums[lflag - i]
                #     lflag = length - i
                l_sorted = False
            # print(nums[1 + j:length - j])
            print(nums, rflag)
        if l_sorted or r_sorted:
            break
    return count


if __name__ == '__main__':
    l = []
    size = range(random.randint(5, 15))
    size = 100
    for _ in range(size):
        l.append(random.randint(-100, 100))
    l1 = [-85, -33, -54, -76, 97, -12, 54, -65, 84, 20, 84, -38, 45, 67, 73]
    l1a = [-85, -33, -54, -76, 97, -12, 54, -65, 84, 20, 84, -38, 45, 67, 73]
    l2 = [-85, -33, -54, -76, 97, -12, 54, -65, 84, 20, 84, -38, 45, 67, 73]
    l2a = [-85, -33, -54, -76, 97, -12, 54, -65, 84, 20, 84, -38, 45, 67, 73]
    l3 = [-85, -33, -54, -76, 97, -12, 54, -65, 84, 20, 84, -38, 45, 67, 73]
    l3a = [-85, -33, -54, -76, 97, -12, 54, -65, 84, 20, 84, -38, 45, 67, 73]
    l3b = [-85, -33, -54, -76, 97, -12, 54, -65, 84, 20, 84, -38, 45, 67, 73]
    # l1 = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    # l1a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    # l2 = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    l3b = [9, 8, 7, 6, 5, 4, 3, 2, 1, 10]
    # print(l)
    # print(bubbles_01(l1))
    # print(bubbles_01_a(l1a))
    # print(bubbles_02(l2))
    # print(bubbles_02_a(l2a))
    # print(bubbles_03(l3))
    # print(bubbles_03_a(l3a))
    print(bubbles_03_b(l3b))
    # print(l)
    # print(check(l1))
    # print(check(l1a))
    # print(check(l2))
    # print(check(l2a))
    # print(check(l3))
    # print(check(l3a))
    print(check(l3b))
